import random
import math


class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y


def distance(city1, city2):
    return math.sqrt((city1.x - city2.x) ** 2 + (city1.y - city2.y) ** 2)


def generate_initial_population(num_individuals, cities):
    """
    随机生成路径序列
    :param num_individuals:
    :param cities:
    :return:
    """
    population = []
    for _ in range(num_individuals):
        individual = random.sample(range(len(cities)), len(cities))
        population.append(individual)
    return population


def fitness(individual, cities):
    """
    计算每个个体的目标值
    :param individual:
    :param cities:
    :return:
    """
    total_distance = 0
    for i in range(len(individual)):
        from_city = cities[individual[i]]
        to_city = cities[individual[(i + 1) % len(individual)]]
        total_distance += distance(from_city, to_city)
    return total_distance


def selection(population, cities):
    """
    查看并选取哪些个体具有较强竞争力，使用总目标值作为概率归一化分母
    :param population:
    :param cities:
    :return:
    """
    fitnesses = [fitness(individual, cities) for individual in population]
    total_fitness = sum(fitnesses)
    probabilities = [fitness / total_fitness for fitness in fitnesses]
    parents = random.choices(population, weights=probabilities, k=2)
    return parents


def crossover(parent1, parent2):
    """
    选取随机长度片段将两个父母的路径合并，继承的部分位置与parent1相同，剩余部分从parent2继承，parent2继承得到的顺序会因为parent1的改变
    :param parent1:
    :param parent2:
    :return:
    """
    start = random.randint(0, len(parent1) - 1)
    end = random.randint(start + 1, len(parent1))
    child = [None] * len(parent1)
    for i in range(start, end):
        child[i] = parent1[i]
    remaining_cities = [city for city in parent2 if city not in child]
    j = 0
    for i in range(len(child)):
        if child[i] is None:
            child[i] = remaining_cities[j]
            j += 1
    return child


def mutation(individual):
    """
    变异，随机交换两个位置
    :param individual:
    :return:
    """
    mutation_rate = 0.01
    if random.random() < mutation_rate:
        index1 = random.randint(0, len(individual) - 1)
        index2 = random.randint(0, len(individual) - 1)
        individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual


def genetic_algorithm(cities, num_generations, population_size):
    population = generate_initial_population(population_size, cities)
    for generation in range(num_generations):
        new_population = []
        while len(new_population) < population_size:
            parent1, parent2 = selection(population, cities)
            child = crossover(parent1, parent2)
            child = mutation(child)
            new_population.append(child)
        population = new_population
    best_individual = min(population, key=lambda x: fitness(x, cities))
    return best_individual


# 示例用法
cities = [City(0, 0), City(1, 2), City(3, 1), City(5, 3), City(2, 5)]
best_path = genetic_algorithm(cities, num_generations=100, population_size=100)
print("Best path:", best_path)
total_distance = fitness(best_path, cities)
print("Total distance:", total_distance)

# 在文本对齐中，可以按照注释和经典相似概率作为交叉对象，社区中与周围句子的相似度（1-p）作为变异概率